<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    var findTargetSumWays = function (nums, S) {
      let sum = 0;
      for (let num of nums) {
        sum += num;
      }

      // S大于sum，不可能实现，返回0
      if (S > sum) {
        return 0;
      }

      // 如果S + sum不是偶数，不可能实现，返回0
      if ((S + sum) % 2 == 1) {
        return 0;
      }

      let target = Math.floor((S + sum) / 2);
      let dp = Array(target + 1).fill(0);
      dp[0] = 1;

      for (let num of nums) {
        for (let j = target; j >= num; j--) {
          dp[j] = dp[j] + dp[j - num];
        }
      }

      return dp[target];
    };
    console.log(findTargetSumWays([1, 1, 1, 1, 1], 3));
  </script>
</body>

</html>